package com.lw.leetcode.hash.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 面试题 17.15. 最长单词
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/27 15:19
 */
public class LongestWord {


    public static void main(String[] args) {
        LongestWord test = new LongestWord();

        // dogwalker
//        String[] arr = {"cat","banana","dog","nana","walk","walker","dogwalker"};
        String[] arr = {"aaaa", "aaa", "aa", "a"};
//        String[] arr = {""};
//
        String s = test.longestWord(arr);
        System.out.println(s);
    }

    private String ans;

    public String longestWord(String[] words) {
        ans = "";
        Map<Character, List<String>> map = new HashMap<>();
        for (String s : words) {
            if ("".equals(s)) {
                continue;
            }
            map.computeIfAbsent(s.charAt(0), v -> new ArrayList<>()).add(s);
        }
        Arrays.sort(words, (a, b) -> a.length() == b.length() ? a.compareTo(b) : b.length() - a.length());
        for (String word : words) {
            if (find(0, word, map)) {
                break;
            }
        }
        return ans;
    }

    private boolean find(int index, String word, Map<Character, List<String>> map) {
        if (index == word.length()) {
            ans = word;
            return true;
        }
        char w = word.charAt(index);
        if (!map.containsKey(w)) {
            return false;
        }
        List<String> list = map.get(w);
        for (String s : list) {
            if (s.equals(word) || s.length() > word.length() - index || !word.substring(index, index + s.length()).equals(s)) {
                continue;
            }
            if (find(index + s.length(), word, map)) {
                return true;
            }
        }
        return false;
    }

}
